package exercise;

import java.util.Arrays;

public class Heap {
    private int elem[];
    private int usedSize;

    public Heap() {
        elem = new int[10];
    }

    public int[] createBigHeap(int[] array) {
        for (int i = 0; i < array.length; i++) {
            elem[i] = array[i];
            usedSize++;
        }
        for (int parent = (array.length - 2) / 2 ; parent >= 0 ; parent--) {
            siftDown(parent,usedSize - 1);
        }
        return elem;
    }

    private void siftDown(int parent, int end) {
        int child = parent * 2 + 1;
        while (child <= end) {
            if (child + 1 <= end && elem[child] < elem[child + 1]) {
                child++;
            }
            if (elem[parent] < elem[child]) {
                swap(parent, child);
            } else {
                break;
            }
            parent = child;
            child = child * 2 + 1;
        }
    }

    private void swap(int i, int j) {
        int tmp = elem[i];
        elem[i] = elem[j];
        elem[j] = tmp;
    }

    public int poll() {
        if(isEmpty()) return -1;
        int ret = elem[0];
        swap(0,usedSize - 1);
        usedSize--;
        siftDown(0,usedSize - 1);
        return ret;

    }

    private boolean isEmpty() {
        return usedSize == 0;
    }

    public void offer(int val) {
        if (isFull()) {
            elem = Arrays.copyOf(elem,2 * elem.length);
        }
        elem[usedSize++] = val;
        siftUp(usedSize - 1);

    }

    private void siftUp(int child) {
        int parent = (child - 1) / 2;
        while (parent >= 0) {
            if (elem[parent] < elem[child]) {
                swap(parent,child);
                child = parent;
                parent = (child - 1) / 2;
            } else {
                break;
            }
        }
    }

    private boolean isFull() {
        return usedSize == elem.length;
    }

    public int peek() {
        return elem[0];
    }
}
